Write a program to check if a given binary tree is a binary search tree.

Question

Aryan Kumar · Answer

#include andlt;stdio.h>
#include andlt;stdlib.h>
#include andlt;limits.h>
// Define the binary tree node
struct TreeNode {
   int val;
   struct TreeNode* left;
   struct TreeNode* right;
};
// Function to create a new binary tree node
struct TreeNode* newNode(int data) {
   struct TreeNode* node = (struct TreeNode*) malloc(sizeof(struct TreeNode));
   node->val = data;
   node->left = NULL;
   node->right = NULL;
   return node;
}
// Function to check if a binary tree is a binary search tree
int isBSTUtil(struct TreeNode* node, int min, int max) {
   if (node == NULL) {
       return 1;
   }
   if (node->val andlt; min || node->val > max) {
       return 0;
   }
   return (isBSTUtil(node->left, min, node->val - 1) andand isBSTUtil(node->right, node->val + 1, max));
}
int isBST(struct TreeNode* root) {
   return isBSTUtil(root, INT_MIN, INT_MAX);
}
int main() {
   struct TreeNode* root = newNode(4);
   root->left = newNode(2);
   root->right = newNode(5);
   root->left->left = newNode(1);
   root->left->right = newNode(3);
   if (isBST(root)) {
       printf("The binary tree is a binary search tree.
");
   } else {
       printf("The binary tree is not a binary search tree.
");
   }
   return 0;
}
In this program, we define the binary tree node structure and a function to create a new binary tree node. We then define a recursive function
isBSTUtil that takes a node, a minimum value, and a maximum value as arguments, and returns true if the tree rooted at the node is a binary search tree within the given range. We call this function initially with the root of the binary tree and the minimum and maximum possible integer values. The function returns true if the node is NULL (an empty tree) or if the node's value is within the given range and the left and right subtrees are also binary search trees within their respective ranges. We use INT_MIN and INT_MAX to represent the minimum and maximum integer values respectively.
Finally, we define another function isBST that calls 
isBSTUtil with the root of the binary tree and returns the result.
In the main function, we create a binary tree and call the 
isBST function to check if it is a binary search tree. We print the result accordingly.

forum

Write a program to check if a given binary tree is a binary search tree.

Utpal Vishwas

Can you answer this question?

1 Answers

Liked By